给出两个串，我们需要修改最少量的字符，使第一个串和第二个串的相同字母数量相同。在此基础上，需要求出字典序最小的字符串。
贪心方式如下：
设需修改的串（第一个串）为s,被匹配的串（第二个串）为t.
在满足”修改最少量的字符“的前提下，使字典序最小，所以修改上去的串是固定的。
比如
CDBABC
ADCABD
那么修改上去的字母一定是A,D.而且修改上去的顺序一定是AD,不是DA.
再来看s串，它一定有一个C和B被取代。
位置的取舍取决于字典序的变化和该字母的”松弛“程度。
在这个例子里，我们找到第一个C的位置，首先因为已经预处理了C的数量，所以我们知道这个C是可松弛的，即可以取代它，也可以不取代它。在这种情况下，我们比较当前可以填进去的字母的字典序和这个可修改字符的大小，如果可以使字典序变小，那么修改，即，例子中C被取代的情况，这个时候填进去的是A。否则，修改这个字符的松弛度，如果当前字符是可修改字符，并且不可松弛，强行替代它。即例子中一个B被取代的情况，在第二个B的位置填进去D。
答案即为
2
ADBADC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<numeric>
#include<set>
#pragma comment(linker, "/STACK:10240000000,10240000000")
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
#define inf 0x3f3f3f3f
#define debug puts("-----")
#define maxn 50000+4
#define uLL unsigned long long
#define LL long long
char s[100000+5];
char t[100000+5];
int sn[26],tn[26];
int ans[28];
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
scanf("%s%s",s,t);
int len=strlen(s);
for(int i=0;i<len;i++)
sn[s[i]-'A']++;
for(int i=0;i<len;i++)
tn[t[i]-'A']++;
for(int i=0;i<26;i++)
ans[i]=tn[i]>sn[i]?tn[i]-sn[i]:0;
ans[26]=-1;
int cnt=0;
for(int i=0;i<len;i++)
{
int k=s[i]-'A';
if(sn[k]<=tn[k])continue;
if(!tn[k])
{
int j=0;
while(ans[j]==0)j++;
if(j==26)break;
s[i]=j+'A';
cnt++;
ans[j]--;
sn[k]--;
}
else
{
int j=0;
while(ans[j]==0)j++;
if(j==26)break;
if(j>k)
tn[k]--;
else
{
s[i]=j+'A';
ans[j]--;
cnt++;
sn[k]--;
}
}
}
printf("%d\n",cnt);
puts(s);
}
|
EOF